package com.sjb.training.lc;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: 有点儿意思
 * @Description:
 */
public class ListNode {
    int val;
    ListNode  next;
    ListNode(){}
    ListNode(int val){
        this.val = val;
    }
    ListNode(int val,ListNode next){
        this.val = val;
        this.next = next;
    }

    class Solution{
        /**
         * 移除元素
         * @param head
         * @param val
         * @return
         */
        public ListNode removeElements(ListNode head, int val) {
            ListNode dummyHead = new ListNode(-1,head);
            if (head == null){
                return head;
            }
            ListNode pre = dummyHead;
            ListNode cur = head;
            while (cur != null){
                if (cur.val == val){
                    pre.next = cur.next;
                }else{
                    pre= cur;
                }
                cur = cur.next;
            }
            return dummyHead.next;
        }
    }

    /**
     * 设计链表
     */
    class MyLinkedList{
        // size 代表存储链表元素的个数
        int size;
        // 虚拟头节点
        ListNode head;
        // 初始化链表
        public MyLinkedList(){
            size = 0;
            head = new ListNode(0);
        }

        // 获取第index节点的数值，注意index是从0开始的，所以第0个节点就是头节点
        public int get(int index){
            if(index < -1 || index >= size){
                return -1;
            }
            ListNode currentNode = head;
            // 包含虚拟节点 所以查找第index+1个节点
            for (int i = 0; i <= index; i++) {
                currentNode = currentNode.next;
            }
            return currentNode.val;
        }

        // 头部插入节点
        public void addAtHead(int val){
            // 插入的新节点
            ListNode newNode = new ListNode(val);
            ListNode dummyHead = new ListNode(-1, head);
            newNode.next = dummyHead.next;
            dummyHead.next = newNode;
        }

        // 尾部插入节点
        public void addAtTail(int tail){
            ListNode tailNode = new ListNode(tail);
            ListNode dummyNode = new ListNode(-1, head);
            ListNode cur = dummyNode;
            while(cur.next != null){
                cur = cur.next;
            }
            cur.next = dummyNode;
        }

        // 在第n个节点前插入节点
        public void addIndex(int index,int val){
            if (index < 0 || index > size){
                return;
            }
            size++;
            // 找到第n个节点 要保证第n个节点是cur.next 才能在第n个节点之前插入新节点
            ListNode newNode = new ListNode();
            ListNode pre = head;
            for (int i = 0; i < index; i++) {
                pre = pre.next;
            }
            newNode.next = pre.next;
            pre .next = newNode;
        }

        // 删除第n个节点
        public void deleteIndex(int index){
            if (index < -1 || index > size){
                return;
            }
            size--;
            if (index == 0){
                head = head.next;
                return;
            }
            ListNode pre =head;
            // 找到要删除的第n个节点
            for (int i = 0; i < index; i++) {
                pre = pre.next;
            }
            pre.next = pre.next.next;
        }
    }
}
